package april;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-4-29 20:08
 * @description：
 * @modified By：
 * @version:
 */
public class April29 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/house-robber/
     * 需要两个值一个是 现在的最大价值 一个是 上一个最大价值
     * 1. 动态规划 问题分解
     * create time: 2020-4-29 20:09
     * @params [nums]
     * @return int
     */
    public int rob(int[] nums) {
        int preMax = 0;//上一个最大价值
        int max = 0;//最大价值
        for(int i = 0;i<nums.length;i++){
            int temp = max;//记录现在最大的价值 因为这个价值现在是最大的但是如果上一个最大值加上了这次遍历到的值 就说不好谁才是最大的 现在记录的意义是在下一步max可能会变化
            max = Math.max(preMax+nums[i],max); //如果上一次的最大值加上这个值比当前最大值大的话就替换max
            preMax = temp; //现在的值就会变成上一次的
        }
        return max;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/min-cost-climbing-stairs/submissions/
     * 1. 动态规划 把这个问题分解成这一步 我是踩还是不踩
     * 2. 这条楼梯 其实就只有两个选项 1. 踩面前这个楼梯 2. 不踩面前这个楼梯但是踩上一个楼梯
     * 3. 根据上面这条问题就变成了一个if
     * create time: 2020-4-29 20:13
     * @params [cost]
     * @return int
     */
    public int minCostClimbingStairs(int[] cost) {

        int preMin = 0;//上一个最大价值
        int min = 0;//最大价值
        for(int i = 0;i<cost.length;i++){
            int temp = min;
            min = Math.min(min+cost[i],preMin);//判断是踩哪个

            preMin  = temp+cost[i];
        }
        return min;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/integer-break/  整数分解(暴力破解法)
     * https://leetcode-cn.com/problems/integer-break/solution/bao-li-sou-suo-ji-yi-hua-sou-suo-dong-tai-gui-hua-/ 题解
     * 1. 暴力解法
     * 我们把求 n 这个数字的解 一步步缩小 变成 求n-1的解 会有一半的重复 大量的重复计算
     * 比如 10;
     * 1. 1 9 9的最大是20 9可以分解成 4 5(最大) 3 6 2 7 1 8
     * 2. 2 8   8的最大是16 可以分及成 4 4(最大) 3 5 2 6 1 7
     * 3. 3 7 这个是解 ...
     * 4. 4 6
     * ...
     * create time: 2020-4-29 20:30
     * @params [n]
     * @return int
     */
    public int integerBreak(int n) {
        if (n == 2) {
            return 1;
        }
        int res = -1;
        for (int i = 1; i <= n - 1; i++) {
            res = Math.max(res, Math.max(i * (n - i), i * integerBreak(n - i)));
        }
        return res;
    }
    /**
     * create by: 冯涛滔
     * description: 整数分解第一次优化 记忆搜索法
     * 1. 暴力破解法大量的重复计算没有意义 比如要计算10 的话 在递归的过程中 3 4 5这三个会被多次重复计算
     * 2. 解决的办法 使用一个数组 存储 F(n)计算过的值 如果下一次有遍历到 n 这个值需要计算直接从数组拿不需要计算了
     * 3. 整体代码没有太大变化 这个解题思路是 自顶向下的 也就是 从n开始一直计算到 2
     * create time: 2020-4-29 20:45
     * @params [n]
     * @return int
     */
    public int integerBreak2(int n) {
        int[] memory = new int[n + 1];
        return integerBreakHelper(n,memory);
    }
    public int integerBreakHelper(int n,int[] memory) {
        if (n == 2) {
            return 1;
        }
        // memory的初始值为0，如果它不为0，说明已经计算过了，直接返回即可
        if (memory[n] != 0) {
            return memory[n];
        }
        int res = -1;
        for (int i = 1; i <= n - 1; i++) {
            res = Math.max(res, Math.max(i * integerBreakHelper(n - i,memory), i * (n - i)));
        }
        // 将每次计算的结果保存到备忘录数组中
        memory[n] = res;
        return res;
    }
    /**
     * create by: 冯涛滔
     * description: 整数分解 动态规划
     * 1. 记忆搜索是 自顶下的 动态规划是 自下向上的 从3开始 一直到n 因为 012 没有计算的价值
     * 2. 第一层循环代表 当前计算的是 F(n)
     * 3. 第二层循环 对F(n) 进行分解 分解成 f(n-1)...一直分解到f(2)
     * create time: 2020-4-29 21:09
     * @params [n]
     * @return int
     */
    public int integerBreak3(int n) {
        int[] memory = new int[n + 1];
        memory[2] = 1;
        for (int i = 3; i <= n; i++) {
            for ( int j = 1; j <= i - 1; j++) {
                memory[i] = Math.max(memory[i], Math.max(j * memory[i - j], j * (i - j)));
            }
        }
        return memory[n];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
     * 剪绳子 动态规划
     * create time: 2020-4-29 21:23
     * @params [n]
     * @return int
     */
    public int cuttingRope(int n) {
        int[] memory = new int[n + 1];
        memory[2] = 1;
        for (int i = 3; i <=n ; i++) {
            for (int j = 1; j < i; j++) {
                //假设这里i = 5
                // 1. 0,1*memory[5-1](1*2),1*(5-1) (1*4) 最后是4
                //2. 3,2*memory[5-2](2*2),2*(5-2) (3*2)  最后是6
                //3. ...
                memory[i] = Math.max(memory[i],Math.max(j * memory[i-j],j * (i-j)));
            }

        }
        return memory[n];
    }



}
